 fun printInt (a:int) =
    print(Int.toString(a)^" ");

fun getInt () =
    Option.valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn);
    
fun printIntList ( [] ) = ()
  | printIntList ( x::xs ) = 
    let
	val tmp = printInt(x)
    in
	printIntList(xs)
    end;

fun getIntList ( 0 ) = []
  | getIntList ( N:int) = getInt()::getIntList(N-1);

fun split [ ]  = ([ ], [ ]) 
    | split [x] = ([ ], [x])
    | split (x::y::L) =
	let val (A, B) =split L
	in (x::A, y::B) 	
	end;

datatype tree = Empty | Br of tree * int * tree; 

fun trav(Br(t1,a,t2)) = trav(t1)@(a::trav(t2))
    |trav empty = [];

fun listToTree ([] : int list) : tree = Empty
  | listToTree (x::l) = let val (l1, l2) = split l
    	in Br(listToTree l1, x, listToTree l2)
  end;


(*begin*)
fun value(Empty) = NONE
  | value(Br(_, x, _)) = SOME x;

fun treecompare (Empty, Empty) = EQUAL
  | treecompare (Empty, _) = LESS
  | treecompare (_, Empty) = GREATER
  | treecompare (Br(_, x1, _), Br(_, x2, _)) =
      case Int.compare(x1, x2) of
          GREATER => GREATER
        | EQUAL => EQUAL
        | LESS => LESS

fun swapDown(Empty) = Empty
| swapDown(Br(Empty, x, Empty)) = Br(Empty, x, Empty) 
| swapDown(Br(Br(ll, lx, lr), x, Br(rl, rx, rr))) =
if x <= lx andalso x <= rx then Br(Br(ll, lx, lr), x, Br(rl, rx, rr) )
else if lx <= rx andalso x>=rx then Br(swapDown(Br(ll, x, lr)), lx, Br(rl, rx, rr))  
else if rx <= lx andalso x>=lx then Br(Br(ll, lx, lr), rx, swapDown(Br(rl, x, rr)))
else if lx <= x andalso x<=rx then Br(swapDown(Br(ll, x, lr)), lx, Br(rl, rx, rr))
else Br(Br(ll, lx, lr), rx, swapDown(Br(rl, x, rr)))
| swapDown( Br( Br(l, lx, r), x, Empty ) ) =
      if lx < x then
          Br(swapDown(Br(l, x, r)), lx, Empty)
      else
          Br( Br(l, lx, r), x, Empty )
| swapDown(Br(  Empty, x, Br(l, rx, r)  )) =
      if rx < x then
          Br(  Empty, rx, Br(l, x, r)  )
      else
          Br(  Empty, x, Br(l, rx, r)  )

fun heapify(Empty) = Empty
  | heapify(Br(Empty, x, Empty)) = Br(Empty, x, Empty) 
  | heapify(Br(l, x, r)) = swapDown(Br(heapify(l), x, heapify(r)))


(*end*)

val L = getIntList(7);
printIntList (trav(heapify(listToTree L)));
